#
# @lc app=leetcode.cn id=19 lang=python3
#
# [19] 删除链表的倒数第N个节点
#
# https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
#
# algorithms
# Medium (39.05%)
# Likes:    913
# Dislikes: 0
# Total Accepted:    206K
# Total Submissions: 526.6K
# Testcase Example:  '[1,2,3,4,5]\n2'
#
# 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
#
# 示例：
#
# 给定一个链表: 1->2->3->4->5, 和 n = 2.
#
# 当删除了倒数第二个节点后，链表变为 1->2->3->5.
#
#
# 说明：
#
# 给定的 n 保证是有效的。
#
# 进阶：
#
# 你能尝试使用一趟扫描实现吗？
#
#

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# @lc code=start


class Solution:
    '''
    52 ms
    '''

    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head == None or n == 0:
            return head

        i = 0
        lenN = False

        nodeI = head
        nodeJ = head

        while nodeI.next != None:
            i += 1
            nodeI = nodeI.next

            if lenN == True:
                nodeJ = nodeJ.next
            elif i == n:
                lenN = True

        if n == i + 1:
            return head.next

        nodeJ.next = nodeJ.next.next

        return head

# @lc code=end

# class Solution:
#     '''
#     36 ms
#     '''

#     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
#         if head == None or n == 0:
#             return head

#         nodes = [head]
#         current = head
#         while current.next != None:
#             current = current.next
#             nodes.append(current)

#         if n == len(nodes):
#             return head.next
#         if n == 1:
#             nodes[-2].next = None
#             return head

#         nodes[-n - 1].next = nodes[-n + 1]
#         return head
